import javax.swing.JLabel;
//Choose the first element as the "pivot"
//Partition: order a[start+1, N-1] in elements <= pivot and >= pivot
//           i++ search for >= pivot
//           j-- search for <= pivot
//           swap(a[i], a[j]);  i++;  j--;   until   i > j
//Now j < i and pointing to an element < pivot. Swap a[start] and a[j] so that
//the pivot moves to its right place. a[] is now in three parts:
//first with elements  <= pivot  then pivot (j)   and then with elements  >= pivot
//Do recursively 2 calls  QuickSort(&a[start], j-1);   QuickSort(&a[j+1], N-j-1);
class QuickSort<T extends Comparable<T>> extends SortAlgorithm<T> { 
    QuickSort(JLabel listLabel, JLabel timeLabel, JLabel averageTimeLabel, JLabel statusLabel) { 
        super(listLabel, timeLabel, averageTimeLabel, statusLabel);
    }
   
    @Override
    protected void sort() { sort(0, m_list.size() - 1); }

    private void sort (int lo, int hi) {
        if (lo < hi) {
            int pivotIndex = partition(lo, hi);
            //Now pivotIndex = the element with pivot and a[lo, hi] is now in three parts:
            //first with elements  <= pivot  then pivot  and then with elements  >= pivot
            sort(lo, pivotIndex - 1);    // --> sorting  a[lo, pivotIndex-1]
            sort(pivotIndex + 1, hi);    // --> sorting  a[pivotIndex+1, hi]
        }
    }
    
    private int partition(int lo, int hi) {
        T pivot = m_list.get( lo );  //Choose pivot value as the first in the list
        //Now we partition from  lo+1  (since we let pivot stay at  lo) to  hi 
        int i = lo;     //start with one lower since i will increament just BEFORE use (++i)
        int j = hi + 1; //start with one higher since j will decreament just BEFORE use (--j)
        while (true) {
            while (less(++i, pivot)) { if (i == hi) break; }
            while (greater(--j, pivot)) { if (j == lo) break; }
            if (i >= j) break;
            swapElements(i, j);
        } 
        swapElements(lo, j); //Move the pivot into middle, where it belongs
        return j;            //Return the index of the pivot
    }
}
